package WeightBalancedTree;

public class WBTree {
	
	private Node root;
	
	public WBTree(){
		root=null;
	}
	
	public Node getRoot(){
		return root;
	}
	
	@SuppressWarnings("unchecked")
	public Node[] sort(Node[] list){
		for (int i=0; i<list.length; i++){
			for (int j=i+1; j<list.length; j++){
				if (list[i].getObject().compareTo(list[j].getObject())>0){
					Node temp=list[i];
					list[i]=list[j];
					list[j]=temp;
				}
			}
		}
		return list;
	}
	
	public Node weightbalancedTree(Node[] list){
		list=sort(list);
		root=weightbalancedTree(list,0,list.length-1);
		//System.out.println(root);
		return root;
	}
	
	public Node weightbalancedTree(Node[] list, int from, int to){
		if (to< from) return null;
		if (to == from) return list[from];
		int min=Integer.MAX_VALUE;
		int dif;
		int index=-1;
		for (int i=from; i<=to; i++){
			int leftweight=getWeight(list, from, i-1);
			int rightweight=getWeight(list, i+1, to);
			dif=Math.abs(leftweight-rightweight);
			if (dif<=min){
				min=dif;
				index=i;
			}
		}
		list[index].setLeft(weightbalancedTree(list,from, index-1));
		list[index].setRight(weightbalancedTree(list, index+1, to));
		return list[index];
	}
	
	public Node minmaxTree(Node[] list){
		list=sort(list);
		root=minmaxTree(list,0,list.length-1);
		return root;
	}
	
	public Node minmaxTree(Node[] list, int from, int to){
		if (to< from) return null;
		if (to == from) return list[from];
		int min=Integer.MAX_VALUE;
		int maximum=-1;
		int index=-1;
		for (int i=from; i<=to; i++){
			int leftweight=getWeight(list, from, i-1);
			int rightweight=getWeight(list, i+1, to);
			if (leftweight<rightweight){
				maximum=rightweight;
			} else {
				maximum=leftweight;
			}
			if (maximum<=min) {
				min=maximum;
				index=i;
			}
		}
		list[index].setLeft(minmaxTree(list,from,index-1));
		list[index].setRight(minmaxTree(list,index+1,to));
		return list[index];
	}
	
	public Node bisectionTree(Node[] list){
		list=sort(list);
		root=bisectionTree(list, 0, list.length-1);
		return root;
	}
	
	public Node bisectionTree(Node[] list, int from, int to){
		if (to<from) return null;
		if (to == from) return list[from];
		double total = getWeight(list, from, to);
		double half = total/2;
		int index=-1;
		for (int i=from+1; i<=to; i++){
			double ly = getWeight(list, from, i-2)+list[i-1].getChance()/2;
			double lx =getWeight(list, from, i-1)+list[i].getChance()/2;
			if (ly<=half && lx >= half){
				index=i;
				break;
			}
		}
		list[index].setLeft(bisectionTree(list, from, index-1));
		list[index].setRight(bisectionTree(list,index+1,to));
		return list[index];
	}
	
	public int getWeight(Node[] list, int from, int to){
		int weight=0;
		for (int i=from; i<=to; i++){
			weight+=list[i].getChance();
		}
		return weight;
	}
	
	public String toString() 
	 {
	     StringBuffer sb = new StringBuffer();
	     toString(sb, root, " ");
	     return sb.toString();
	 }

	 private void toString(StringBuffer sb, Node aktuell, String s) 
	 {
	     if (aktuell != null) 
	       {
	         toString(sb, aktuell.getRight(), s+"|  ");
	         sb.append(s).append("+--(").append(aktuell);
	         sb.append(") ").append("\n");
	         toString(sb, aktuell.getLeft(), s+"|  ");
	       }
	 }
	 
	 public void printlist(Node[] list){
		 for (int i=0; i<list.length; i++){
			 System.out.println(list[i]);
		 }
	 }
	 
	 public static void main(String[] args){
		 Node n1 = new Node("folz",6);
		 Node n2 = new Node("schurich",40);
		 Node n3 = new Node("grabowski",30);
		 Node n4 = new Node("denzer",24);
		 Node n5 = new Node("loeffler",1);
		 Node n6 = new Node("kretschmer",15);
		 Node n7 = new Node("schlenther",6);
		 Node n8 = new Node("guettler",15);
		 Node[] list={n1,n2,n3,n4,n5,n6,n7,n8};
		 WBTree tree = new WBTree();
		 //tree.printlist(tree.sort(list));
		 tree.minmaxTree(list);
		 System.out.println(tree);
		/* WBTree tree1 = new WBTree();
		 tree1.weightbalancedTree(list);
		 System.out.println(tree1);
		 WBTree tree2 = new WBTree();
		 tree2.bisectionTree(list);
		 System.out.println(tree2);*/
		 tree.printlist(list);
	 }

}
